#include <iostream>
#include <algorithm>
#include <string>
#include <queue>
#include <vector>
#include <cstdio>
#define inf 0x7fffffff
#define maxn 100005
using namespace std;
struct node
{
    int to, val;
    bool operator<(const node &p) const { return val > p.val; };
    node(int to = -1, int val = inf) : to(to), val(val){};
};
int dis[maxn], vis[maxn], n, m, s, u, v, w;
vector<vector<node>> edge;
priority_queue<node> que;
void dij()
{
    fill(dis, dis + n + 1, inf);
    fill(vis, vis + n + 1, 0);
    int now = s;
    dis[s] = 0;
    que.push(node(now, 0));
    while (que.empty() == false)
    {
        node p = que.top();
        que.pop();
        if (vis[p.to] == 1)
            continue;
        vis[p.to] = 1;
        for (auto &it : edge[p.to])
        {
            dis[it.to] = min(dis[it.to], dis[p.to] + it.val);
            if (vis[it.to] == 0)
                que.push(node(it.to, dis[it.to]));
        }
    }
}
int main()
{
    scanf("%d%d%d", &n, &m, &s);
    edge.resize(n + 1);
    for (int i = 0; i < m; ++i)
    {
        scanf("%d%d%d", &u, &v, &w);
        edge[u].push_back(node(v, w));
    }
    dij();
    for (int i = 1; i <= n; ++i)
        printf("%d ", dis[i]);
    return 0;
};